package 我的Java学习_算法基础.day_01;




import java.util.Random;
/*  1-1000这一千个数存放在含有1001个元素的数组中
    只有一个元素是重复的
    求出这个重复的元素
    每个数组元素只访问一次
 */
public class 唯一成对的数 {
    public static void main(String[] args) {
        int N = 11;//1001
        int[] array = new int[N];
        for (int i=0;i<array.length-1;i++){
            array[i]=i+1;
        }
        Random random = new Random();
        //最后一个数是随机数
        array[N-1]=random.nextInt(N-1)+1;
        //随机下标
        int index = random.nextInt(N);
        swap(array,index,array.length-1);
        printArray(array);
        //方法一：按位异或 A^A=0;A^0=A
        //(1^2^3'k''^1000)^(1^2^''K'''K^1000)=k
        int f =0;
        for(int i = 0 ;i<N-1;i++){
            f=f^(i+1);
        }
        for(int i = 0;i<N;i++){
            f=f^array[i];
        }
        System.out.println(f);
        System.out.println("-------------------");
        //方法二：辅助储存空间
        int[] help = new int[N];
        for(int i = 0;i<array.length;i++){
            help[array[i]]++;
        }
        for(int i =0;i< array.length;i++){
            if(help[i]==2){
                System.out.println(i);
            }
        }

    }

    private static void swap(int[] array,int index,int n){
        int f;
        f=array[n];
        array[n]=array[index];
        array[index]=f;
    }

    public static void printArray(int[] array){
        System.out.print("[");
        for (int i = 0;i<array.length-1;i++){
            System.out.print(array[i]+",");
        }
        System.out.println(array[array.length-1]+"]");
    }
}
